package com.example.demo.practice;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * @date 2022/6/7 15:07
 */
public class MyHeap {



   static class Heap{

        int [] arr;
        int index;
        int capicity;

        public Heap(int size) {
            this.arr = new int[size];
            this.capicity = size;
            this.index = 0;
        }

        public void add(int num){
            arr[index++]=num;
            heapUp(index-1);
            heapDown(index-1,capicity);
        }

        public void print(){
            for(int i=0;i<capicity;i++){
                System.out.print(arr[i]+" ");
            }
        }


        public void heapUp(){
            for(int i = 1; i< capicity; i++){
                int index = i;
                while(index > 0 && arr[(index-1)/2] < arr[index]){
                    swap((index-1)/2, index);
                    index = (index-1)/2;
                }
            }
        }

       public void heapUp(int index){
           while(index > 0 && arr[(index-1)/2] < arr[index]){
               swap((index-1)/2, index);
               index = (index-1)/2;
           }
       }


        public void heapDown(int index, int size){
            if(2*index+1 >= size) return;
            int left = arr[2*index+1];
            int right = 2*index+2 < size ? arr[2*index+2] : arr[2*index+1];
            int max = Math.max(left,right);
            int maxIndex = left >= right ? 2*index+1 : 2*index+2;
            while(arr[index] < max && index < size){
                swap(index, maxIndex);
                index = maxIndex;
                if(2*index+1 >= size) return;
                left = arr[2*index+1];
                right = 2*index+2 < size ? arr[2*index+2] : arr[2*index+1];
                max = Math.max(left,right);
                maxIndex = left >= right ? 2*index+1 : 2*index+2;
            }

        }

        public void heapDown(){
            for(int i = capicity-1; i>=0 ;i--){
                int index = i;
                if(2 * index +2 >= capicity) continue;
                int left = arr[2*index+1];
                int right = 2*index+2 < capicity ? arr[2*index+2] : arr[2*index+1];
                int max = Math.max(left,right);
                int maxIndex = left >= right ? 2*index+1 : 2*index+2;
                while(arr[index] < max && index >=0){
                    swap(index, maxIndex);
                    index = maxIndex;
                    if(2*index+1 >= capicity) break;
                    left = arr[2*index+1];
                    right = 2*index+2 < capicity ? arr[2*index+2] : arr[2*index+1];
                    max = Math.max(left,right);
                    maxIndex = left >= right ? 2*index+1 : 2*index+2;
                }
            }
        }

        /**
         * 大根堆排序，将首个值移动到最后面 然后进行heapDown
         */
        public void sort(){
            int size = capicity;
            for(int i=0;i<capicity;i++){
                swap(0,size-1);
                heapDown(0, size--);
            }
        }

        public void swap(int i, int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

    }


    public static void main(String[] args) {

       int x = 1/2;
        System.out.println(x);
        Heap heap = new Heap(10);
        heap.add(2);
        heap.add(5);
        heap.add(6);
        heap.add(15);
        heap.add(1);
        heap.print();
        heap.sort();
        System.out.println();
        heap.print();
    }




}
